package com.mlh.greed;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author 缪林辉
 * @date 2024/4/12 12:56
 * @DESCRIPTION
 */
// 有一些球形气球贴在一堵用 XY 平面表示的墙面上。
// 墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。
// 你不知道气球的确切 y 坐标。
// 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。
// 在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。
// 可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
// 给你一个数组 points ，返回引爆所有气球所必须射出的 最小弓箭数 。

// 输入：points = [[10,16],[2,8],[1,6],[7,12]]
// 输出：2
// 解释：气球可以用2支箭来爆破:
// -在x = 6处射出箭，击破气球[2,8]和[1,6]。
// -在x = 11处发射箭，击破气球[10,16]和[7,12]。

public class 用最少数量的箭引爆气球 {
    //本题自己写出，但是不知道如何描述解题想法，看代码随想录写出本题想法的描述

    // 直觉上来看，貌似只射重叠最多的气球，用的弓箭一定最少，那么有没有当前重叠了三个气球，我射两个，留下一个和后面的一起射这样弓箭用的更少的情况呢？
    // 显然不会，留下的那一个气球并不会让后面的气球多被射中一点，撑死和后面的一起被射中
    // 那么就试一试贪心吧！局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。
    //为了让气球尽可能的重叠，需要对数组进行排序。
    //按照起始位置排序，那么就从前向后遍历气球数组，靠左尽可能让气球重复。
    public int method1(int[][] points) {
        //排序
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]>o2[0]){
                    return 1;
                }else if(o1[0]==o2[0]&&o1[1]>o2[1]){//如果起始位置相同，结束位置小的排在前面
                    return 1;
                }else{
                    return -1;
                }
            }
        });
        //排完序后
        //先以第1个气球为标准，看看后面的气球的最小值有没有大于第1个气球的最大值，如果大于的话两者没有一点重叠，不可能被一起射中
        //如果后面的气球的最小值小于第1个气球的最大值，此时还需要判断，后面气球的最大值是否小于第1个气球的最大值
        //需要更新index，index等于后面气球的最大值，为什么呢？ 因为如果不更新，会导致最终要射的位置，会超过这个气球最大值
        //导致它根本无法被射中，因此更新index保证这个气球能被射中
        //上面是原因，代码总结的话就是 ：重叠气球中的右边边界的最小值之前的区间一定需要一个弓箭。
        int num=1;
        int index=points[0][1];
        for (int i = 1; i < points.length; i++) {
            if(index<points[i][0]){
               num++;
               index=points[i][1];
            }else{
                if(index>points[i][1]){
                    index=points[i][1];
                }
            }
        }
        return num;
    }
    // public static void main(String[] args) {
    //     int [][]points={{9, 12}, {1, 10}, {4, 11}, {8, 12}, {3, 9}, {6, 9}, {6, 7}};
    //     Arrays.sort(points, (o1, o2) -> {
    //         if(o1[0]>o2[0]){
    //             return 1;
    //         }else if(o1[0]==o2[0]&&o1[1]>o2[1]){
    //             return 1;
    //         }else{
    //             return -1;
    //         }
    //     });
    //     System.out.println(Arrays.deepToString(points));
    // }
}
